import javax.swing.*;

public class Test {
    public static void main(String[] args) {

    }
}

/*class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }*/
  //二叉树的最近公共祖先
/*class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left =lowestCommonAncestor(root.left,p,q);
        TreeNode right =lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null) {
            return root;
        }
        else if (left != null) {
            return left;
        }
        else if (right != null) {
            return right;
        }
        return  null;

    }
}*/


 class TreeNode {
      int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

  //从前序与中序遍历序列构造二叉树
/*class Solution {
     public int size = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChile(preorder,inorder,0, preorder.length-1);
    }
    private TreeNode buildTreeChile (int[] preorder, int[] inorder,int inbe, int ined){
        if (inbe > ined){
            return null;
        }
        TreeNode root = new TreeNode(preorder[size]);
        int rootin = findroot(inorder,inbe,ined,preorder[size]);
        if (rootin == -1) {
            return null;
        }
        size++;
        root.left = buildTreeChile(preorder, inorder, inbe, rootin-1);
        root.right = buildTreeChile(preorder, inorder,rootin+1,ined);

        return root;
    }
    private int findroot(int[] inorder,int inbe , int ined , int key){
        for (int i = inbe; i <= ined; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}*/

//从中序与后序遍历序列构造二叉树.

/*
class Solution {
    public int size;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        size = postorder.length-1;
        return buildTreeChile(postorder,inorder,0, inorder.length-1);
    }
    private TreeNode buildTreeChile (int[] postorder, int[] inorder,int inbe, int ined){
        if (inbe > ined){
            return null;
        }
        TreeNode root = new TreeNode(postorder[size]);
        int rootin = findroot(inorder,inbe,ined,postorder[size]);
        if (rootin == -1) {
            return null;
        }
        size--;
        root.right = buildTreeChile(postorder, inorder,rootin+1,ined);

        root.left = buildTreeChile(postorder, inorder, inbe, rootin-1);


        return root;
    }
    private int findroot(int[] inorder,int inbe , int ined , int key){
        for (int i = inbe; i <= ined; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}*/
//根据二叉树创建字符串
/*
class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strchild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void  tree2strchild (TreeNode root,StringBuilder stringBuilder){
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append("(");
            tree2strchild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if (root.right != null) {
                stringBuilder.append("()");
            }
            */
/*if (root.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }*//*

        }
        if (root.right != null) {
            stringBuilder.append("(");
            tree2strchild(root.right,stringBuilder);
            stringBuilder.append(")");
        }*/
/*else {
            return;
        }*//*

    }
}
*/
